ในหลายกรณีการเลือกใช้ data structure ที่ไม่เหมาะสมนำไปสู่การพัฒนา algorithm ที่ซับซ้อนเกินความจำเป็น ในเอกสารนี้จะแนะนำ container ที่ใช้บ่อย 2 ชนิด ซึ่งสามารถเรียกใช้ได้โดยสะดวกจาก statndard library
Container ที่จะพูดถึงในเอกสารนี้คือ vector และ unordered_map ซึ่งทั้งคู่มีการใช้งานบ่อย โดยมีเนื้อหาดังนี้
Vector ชื่ออาจจะทำให้เราสับสนกัน vector ในวิชาคณิตศาสตร์ โดย vector ใน STL มีความหมายบ้างอย่างที่ใช้ร่วมกับวิชาคณิตศาสตร์ เช่น มีสมาชิกได้มากกว่า 1 ตัว แต่มีหลายความหมายที่ไม่เหมือนในคณิตศาสตร์ เช่น สมาชิกสามารถเป็น data type ที่ไม่ใช่ตัวเลข (char, string and object)
vector ทำหน้าที่คล้ายกับ array โดย vector มีความสามารถในการเพิ่มหรือลดจำนวนสมาชิก vector ใช้การจองทรัพยากรหน่วยความจำแบบ dynamic
สังเกตการใช้ auto ใน for loop
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> v = {7, 5, 16, 8};
v.push_back(25);
v.push_back(13);//
for(auto &i : v) {
cout << i <<" ";
}
}
Running /home/ubuntu/workspace/main.cc
7 5 16 8 25 13มีน้อยครั้งที่เราจะกำหนดขนาดเริ่มต้นของ vector แต่ถ้าจำเป็นต้องทำ เราสามารถใช้คำสั่ง resize() ซึ่งสามารถกำหนดค่าเริ่มต้นได้ด้วย
#include <iostream>
#include <vector>
using namespace std;
int main (){
vector<int> v={1,1,1};
for (int i=4;i<7;i++) v.push_back(i);
v.resize(10);
v.resize(15,100);
cout << "myvector contains:";
for (auto &i: v){
cout<<i<<" ";
}
return 0;
}
Running /home/ubuntu/workspace/main.cc
myvector contains:1 1 1 4 5 6 0 0 0 0 100 100 100 100 100ใช้ iterator เพื่อเข้าถึงข้อมูล
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> v = {7, 5, 16, 8};
for (vector<int>::iterator i = v.begin() ; i != v.end(); ++i){
cout<< *i <<" ";
}
}
Running /home/ubuntu/workspace/main.cc
7 5 16 8
การใช้
#include <iostream> // std::cout
#include <algorithm> // std::lower_bound, std::upper_bound, std::sort
#include <vector> // std::vector
using namespace std;
int main () {
int myints[] = {10,20,30,30,20,10,10,20};
vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20
//sorting by using introsort algorithom O(nlogn)
sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30
//finding boundaries by using
//binary search algorithom O(logn)
vector<int>::iterator low,up;
low=lower_bound (v.begin(), v.end(), 20); //__________^
up= upper_bound (v.begin(), v.end(), 20); //___________________^
std::cout << "20 starts at position " << (low- v.begin()) << '\n';
std::cout << "20 ends before position " << (up - v.begin()) << '\n';
return 0;
}
Running /home/ubuntu/workspace/main.cc
20 starts at position 3
20 ends before position 6
#include <iostream> //cout
#include <utility> //pair
using namespace std;
int main () {
pair<string,string> x={"friend","foe"};
pair<int,string>y;
y={3,"kings"};
cout<<x.first<<" "<<x.second<<endl;
cout<<y.first<<" "<<y.second<<endl;
return 0;
}
Running /home/ubuntu/workspace/main.cc
friend foe
3 kings
unordered_map เป็น data structure ที่ถูกออกแบบมาเพื่อเก็บข้อมูลในรูปแบบ key,value ในรูปแบบ hashtable
#include <iostream>
#include <unordered_map>
using namespace std;
int main(){
std::unordered_map<int,int> m = {{5,4},{7,8},{9,10}};
m[5]=3;
m[11]=1;
for(auto &i : m) {
cout<<"key: "<< i.first <<" value:"<< i.second <<endl;
}
}
Running /home/ubuntu/workspace/main.cc
key: 11 value:1
key: 9 value:10
key: 5 value:3
key: 7 value:8#include <iostream>
#include <unordered_map>
using namespace std;
int main () {
unordered_map<string,string> m={{"Hello","World!"},{"foo","bar"}};
unordered_map<string,string>::iterator i;
i=m.find("foo");
if(i==m.end())
cout<<"Not found";
else
cout << i->second << endl;
return 0;
}
Running /home/ubuntu/workspace/main.cc
bar
queue ที่มีสมาชิกมากที่สุด(หรือน้อยที่สุด)อยู่บนสุด
#include <iostream>
#include <queue>
using namespace std;
int main () {
priority_queue<int, vector<int>, greater<int> > Qa;
priority_queue<int> Qb;
Qa.push(1); Qb.push(1);
Qa.push(3); Qb.push(3);
Qa.push(2); Qb.push(2);
Qa.push(4); Qb.push(4);
printf("Qa: ");
while( !Qa.empty() ){
printf("%d ",Qa.top() );
Qa.pop();
}
printf("\nQb: ");
while( !Qb.empty() ){
printf("%d ",Qb.top() );
Qb.pop();
}
}
Running /home/ubuntu/workspace/priority_q.cpp
Qa: 4 3 2 1
Qb: 1 2 3 4#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Node{
int dist;
};
bool operator>( const Node& L, const Node& R ) {
return L.dist > R.dist;
}
int main () {
Node n1,n2,n3,n4;
priority_queue< Node, vector<Node>, greater<Node> > Q;
n1.dist=3; Q.push(n1);
n2.dist=1; Q.push(n2);
n3.dist=2; Q.push(n3);
n4.dist=4; Q.push(n4);
printf("Q: ");
while( !Q.empty() ){
printf("%d ",Q.top().dist );
Q.pop();
}
}
Running /home/ubuntu/workspace/priority_q.cpp
Q: 1 2 3 4A set contains unique members and always be sorted
#include <iostream>
#include <set>
using namespace std;
int main (){
set< pair<int,int> > S;
set< pair<int,int> >::iterator it;
S.insert({3,2});
S.insert({1,4});
S.insert({4,5});
S.insert({1,6});
S.insert({4,5});
printf("S contains:");
while( !S.empty() ){
it=S.begin();
printf(" {%d, %d}", it->first, it->second );
S.erase(it);
}
return 0;
}
Running /home/ubuntu/workspace/set.cpp
myset contains: {1, 4} {1, 6} {3, 2} {4, 5}#include <iostream>
#include <unordered_map>
using namespace std;
struct Node{
float dist;
int prev_node;
unordered_map<int,float> edges;
};
int main () {
int n;
unordered_map<int,Node> G;
scanf("%d",&n);
for(int i=0;i<n;i++){
int a,b;
float s;
scanf("%d%d%f",&a,&b,&s);
G[a].dist=999;
G[a].prev_node=-1;
G[a].edges[b]=s;
G[b].dist=999;
G[b].prev_node=-1;
G[b].edges[a]=s;
}
for(auto node: G){
printf("\nG[%d]:",node.first);
for(auto edge : node.second.edges){
printf(" {%d,%.00f}",edge.first,edge.second);
}
}
}
9 6
1 3 1
1 2 5
3 2 2
3 4 6
2 4 3
2 5 7
4 5 4
4 6 9
5 6 5
In [ ]: